General Background
This invention relates to image processing methods and more particularly to methods of detecting a known pattern or model in an unknown image.
Suppose that we have an engineering diagram containing a number of symbols of known shape. Such a symbol can be, for example, a circle with a cross through it indicating where a drill press should place holes in a part being fabricated. Suppose further that we want to use a computer or image processing device automatically to determine the locations of these symbols.
To solve this problem, we can begin by scanning the paper diagram with a scanner to produce into a digital image that is suitable for processing by the computer or image processing device. Then the computer can search the digitized image for a pattern of bits that corresponds to the symbols. The computer then outputs a message to notify us of its finding, or perhaps automatically takes an action (e.g., a computer-controlled drill press might automatically drill holes in the part at the determined locations) based on its finding.
This problem is more complicated in practice than it might at first appear. There can be many such symbols on any given diagram, and each diagram can be quite large. Moreover, the digital (scanned) image of the diagram may be of poor quality due to, for example, FAX transmission, multiple generations of photocopying, user-added marks such as deliberate hand-written annotations as well as stray or erroneous marks, skewed image produced by misalignment of paper and scanner, etc., etc. The appearance of each symbol can therefore deviate significantly from its ideal appearance; nevertheless, we want to locate each symbol reliably and efficiently.
Known methods of finding patterns include using Hausdorff distance matching of binary images. For example, see the references [HR93], [Ruc95a], and [Ruc95b] (described more fully in the Background References section immediately below). The Hausdorff distance is a function that measures the similarity between two point sets. It is a reliable measure of similarity even when the points in the sets have been perturbed or deleted, when noise points have been added, and when one set corresponds only to a small subregion of the other set. These properties make it useful for document analysis, among other tasks. However, known methods for its computation are not as fast or as memory-efficient as is desired. That is, the known methods require computation times and memory resources that are excessive, even prohibitive, in certain application domains. Accordingly, better methods are needed.